//
//  FindKthLargest.swift
//  LeetCodeDemo
//
//  Created by OS on 2022/7/29.
//

import Foundation

class FindKthLargest {
    func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
        let n = nums.count
        if n < k {
            return -1
        }
        
        // 建堆
        var temp = nums
        buildHeap(&temp, k - 1)
        for i in k..<temp.count {
            if temp[0] < temp[i] {
                temp[0] = temp[i]
                heapify(&temp, k - 1, 0)
            }
        }
        return temp[0]
    }
    
    func buildHeap(_ nums: inout [Int], _ n: Int) {
        var i = n / 2
        while i >= 0 {
            heapify(&nums, n, i)
            i -= 1
        }
    }
    
    func heapify(_ nums: inout [Int], _ n: Int, _ i: Int) {
        var i = i
        while true {
            var minPos = i
            let left = 2 * i + 1
            if left <= n && nums[left] < nums[minPos] {
                minPos = left
            }
            let right = 2 * i + 2
            if right <= n && nums[right] < nums[minPos] {
                minPos = right
            }

            if minPos == i {
                break
            }
            nums.swapAt(i, minPos)
            i = minPos
        }
    }
    
    func test() {
        let nums = [3,2,3,1,2,4,5,5,6], k = 4
        let res = findKthLargest(nums, k)
        print(res)
    }
    
}

class FindKthLargest01 {
    
}
